/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
  /*** error
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* dummmyHead = new ListNode(0);
        dummmyHead->next = pHead;
        ListNode* insert = dummmyHead;
        ListNode* pre = dummmyHead, *cur = pHead;
        while(cur){
            if(cur->val < x){
                pre->next = cur->next;
                cur->next = insert->next;
                insert->next = cur;
                insert = cur;
            }
            cur = cur->next;
        }
        return dummmyHead->next;
    }****/

    ListNode* partition(ListNode* pHead, int x) {
        if(pHead == nullptr)
            return nullptr;
        // 设置两个头节点
        ListNode* lowHead = new ListNode(-1);  // 指向所有<X的节点链表
        ListNode* upHead = new ListNode(-1);   // 指向所有>=X的节点的链表
        ListNode* cur = pHead;
        ListNode* pl = lowHead, *pu = upHead;
        while(cur != nullptr){
            if(cur->val < x){
                pl->next = cur;
                pl = cur;
            }
            else{
                pu->next = cur;
                pu = cur;
            }
            cur = cur->next;
        }
        // 合并
        pu->next = nullptr;
        pl->next = upHead->next;
        
        return lowHead->next;
    }
    
};